import java.util.Arrays;

public class Sort2 {

    // 直接插入排序
    public static void insertSort1(int[] array) {
        for(int i = 1; i < array.length; i++) {
            // 记录 i 下标的元素，防止比 i下标 大的元素向后移动将其覆盖
            int tmp = array[i];
            // 从下标为 i-1的元素开始遍历， 比 array[i]大的元素都向后移动
            int j = i -1;
            for(; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    // 此时array[j] < array[i]，且 j + 1下标 为 array[i] 在已排序元素中的位置
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    // 折半插入排序
    public static void binaryInsertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int left = 0, right = i - 1;
            int mid = (left + right) / 2;
            int target = array[i];      // 待插入的元素
            // 1. 找到合适的插入位置
            while(left <= right) {
                mid = (left + right) / 2;
                if(array[mid] < target) left = mid + 1;
                // 出现 array[mid] == target,同样进行此操作，可保证 元素插入下标的一致性
                else right = mid -1;
            }
            // 2. 在已排序好的数组区间中，将mid开始的元素，从后向前依次向后移动
            for (int j = i - 1; j >= right + 1; j--) {
                array[j+1] = array[j];
            }
            // 3. 将 array[i] 插入到 mid 位置
            array[right + 1] = target;
        }
    }

    // 选择排序
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            // 需要找 n - 1 次， 每次从第一个元素开始向后遍历
            int maxIndex = 0;
            for (int j = 1; j < array.length - i; j++) {
                if(array[j] > array[maxIndex]) maxIndex = j;
            }
            swap(array, array.length - 1 - i, maxIndex);
        }
    }
    private static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }


    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            // 判断是否继续冒泡排序
            int flag = 1;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flag = 0;
                }
            }
            if(flag == 1) break;
        }
    }




    
    public static void heapSort2(int[] array) {
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }
    }
    private static void createBigHeap(int[] array) {
        for(int parent = (array.length-2) / 2; parent >= 0; parent-- ) {
            shiftDown(array,parent, array.length);
        }
    }
    private static void shiftDown(int[] array, int root, int len) {
        int parent = root;
        int child = root * 2 + 1;
        while(child < len) {
            if(child + 1 < len && array[child] < array[child+1]) {
                child = child + 1;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

    public static void countSort(int[] array) {
        int minVal = array[0];
        int maxVal = array[0];
        // 找到数组元素的最大值和最小值
        for (int i = 1; i < array.length; i++) {
            if(array[i] < minVal) minVal = array[i];
            if(array[i] > maxVal) maxVal = array[i];
        }
        int[] countArray = new int[maxVal - minVal + 1];
        // 记录每个元素出现的次数
        count(array, countArray , minVal);
        //把排序好的数据写回到 tmpArray 数组中
        int k = 0;
        for (int i = 0; i < countArray.length; i++) {
            while(countArray[i] > 0) {
                array[k++] = i + minVal;
                countArray[i]--;
            }
        }
    }
    private static void count(int[] array, int[] countArray, int minVal) {
        for (int i = 0; i < array.length; i++) {
            countArray[array[i] - minVal]++;
        }
    }


    // 快排
    public static void quiackSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        //代表此时 此时排序区间 只有一个元素 或者 排序区间不存在
        if(left >= right) return;

        // 在 partition方法中，完成分区操作，并返回 pivot的下标
        int pivot = partition(array, left, right);
        // 对 pivot 的左右区间进行递归操作
        quick(array,pivot + 1, right);
        quick(array,left, pivot - 1);
    }

    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;
        while(left < right) {
            //必须先让 right 去寻找比tmp小的元素， 因为这样可以防止 一个大的元素 被错误地放到 数组的前面
            while(left < right && array[right] >= tmp) right--;
            while(left < right && array[left] <= tmp) left++;

            //此时 left 和 right 分别指向 大于和小于 tmp的元素
            swap(array,left,right);
        }
        swap(array, i, right);
        return right;
    }



    // 快速排序   挖坑法
    public static void quickSort2(int[] array) {
        quick2(array, 0, array.length - 1);
    }
    private static void quick2(int[] tmpArray, int left, int right) {
        if(left >= right) return;       //代表此时 此时排序区间 只有一个元素 或者 排序区间不存在

        // 在 partition方法中，完成分区操作，并返回 pivot的下标
        int pivot = partition2(tmpArray, left, right);
        // 对 pivot 的左右区间进行递归操作
        quick2(tmpArray, left, pivot - 1);
        quick2(tmpArray, pivot + 1, right);
    }
    private static int partition2(int[] tmpArray, int left, int right) {
        int tmp = tmpArray[left];
        while(left < right) {
            //必须先让 right 去寻找比tmp小的元素， 因为这样可以防止 一个大的元素 被错误地放到 数组的前面
            while(left < right && tmpArray[right] >= tmp) right--;
            // right “指针” 入左坑
            swap(tmpArray, left, right);
            while(left < right && tmpArray[left] <= tmp) left++;
            // left “指针” 入右坑
            swap(tmpArray, left, right);
        }
        tmpArray[left] = tmp;
        return left;
    }



    //归并排序
    public static void mergeSort(int[] array) {
        merge(array, 0 , array.length - 1);
    }
    private static void merge(int[] array, int left, int right) {
        if(left >= right) return;

        //分解小区间
        int mid = (left + right) / 2;
        merge(array, left, mid);
        merge(array, mid + 1, right);

        //合并小区间的有序数组
        int start1 = left;
        int start2 = mid + 1;
        int[] mergeArray = new int[right - left + 1];
        int k = 0;
        while(start1 <= mid && start2 <= right) {
            if(array[start1] <= array[start2]) {
                mergeArray[k++] = array[start1++];
            }else {
                mergeArray[k++] = array[start2++];
            }
        }
        while(start1 <= mid) {
            mergeArray[k++] = array[start1++];
        }
        while(start2 <= right) {
            mergeArray[k++] = array[start2++];
        }
        //将mergeArray数组中的元素 放回到 原来数组的合并区间内
        k = 0;
        while (left <= right) {
            array[left++] = mergeArray[k++];
        }
    }




    // 希尔排序
    public static void shellSort(int[] array){
        // 当前数组只有一个元素，不需要进行排序
        if(array.length < 2) return;

        // 保证第一次的 gap = n/2,最后一次排序 gap = 1
        int gap = array.length;
        while(gap > 1) {
            gap = gap / 2;
            shell(array, gap);
        }
    }
    private static void shell(int[] array, int gap) {
        for(int i = gap; i < array.length; i++) {
            int tmp = array[i];
            // 若array[j] > tmp，则该元素向前移动
            // j 继续向前移动 gap 个位置，重复上述过程，直到 array[j] <= tmp 或 j < 0
            int j = i - gap;
            for(; j >= 0; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }




    // 基数排序
    public static void radixSort(int[] array) {
        // 1. 先获得所有元素中的最大位数
        int count = 1;          // 记录最大位数
        int multiple = 10;      // 记录当前倍数
        for (int x : array) {
            while (x / multiple > 0) {
                multiple *= 10;
                count++;
            }
        }

        // 2. 采用“最低位优先法”进行 count 次“分配”与“收集”
        multiple = 1;       // 描述当前关键字的取值方式
        for (int i = 0; i < count; i++) {
            // 准备 0~9，总共10个桶存放元素
            int[][] buckets = new int[10][0];
            for (int j = 0; j < 10; j++) {
                buckets[j] = new int[0];
            }
            // 针对关键字进行“分配”
            for (int x : array) {
                int key = x / multiple % 10;
                int len = buckets[key].length;
                buckets[key] = Arrays.copyOf(buckets[key], len + 1);
                buckets[key][len] = x;
            }
            // 对元素按顺序收集
            int k = 0;
            for (int j = 0; j < 10; j++) {
                // 遍历每个桶
                for (int x : buckets[j]) {
                    array[k++] = x;
                }
            }
            multiple *= 10;
        }
    }





}
